package medium

import (
	. "GoLeetcode/common"
)

/*
时间复杂度：O(N)
空间复杂度：O(1)

解决：首先通过双指针找到a与b（或b与a）之间的a的前缀与b的后缀之间的最长公共部分
	然后判断b中[i,j]部分是否是回文，如果是则符合条件
*/

func checkPalindromeFormation(a string, b string) bool {
	return check(a, b) || check(b, a)
}

// 判断a的前缀与b的后缀是否构成回文串
func check(a, b string) bool {
	i, j := 0, len(b)-1
	for i < j && a[i] == b[j] {
		i++
		j--
	}
	// 这里非常重要，例如a: abcdeduio b: lmnghjcba
	// abc 与 cba匹配，但是a中剩下的ded也是回文，也就是说a可以分为 abcded前缀，b可以分为cba后缀
	// 所以最后也是符合条件的，所以这里需要加上 isPalindrome(a, i, j)
	return isPalindrome(a, i, j) || isPalindrome(b, i, j)
}

// isPalindrome 判断是否是回文串1
func isPalindrome(s string, i, j int) bool {
	for i < j && s[i] == s[j] {
		i++
		j--
	}
	return i >= j
}

/*
时间复杂度：O(N)
空间复杂度：O(1)

解决：中心扩展，假设字符串长度为N, 则从最中间开始(n/2-1), 使用left和right双指针
left往左边，right往右边，找到a或b中从中线开始最长的一段回文串，
然后判断除去中间这段，a的前半部分与b的后半部分是否构成回文(或b的前半与a的后半)
*/

func checkPalindromeFormation1(a string, b string) bool {
	left := len(a)/2 - 1
	// 找到a或b中间最长的一段回文串
	left = Min(check1(a, a, left), check1(b, b, left))
	left = Min(check1(a, b, left), check1(b, a, left))
	return left == -1
}

func check1(a string, b string, left int) int {
	right := len(a) - 1 - left
	for left >= 0 && a[left] == b[right] {
		left--
		right++
	}
	return left
}
